﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

    1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

    1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

     * 
     * */
    class Problem31
    {
        static List<int> _values = new List<int>()
            {
                200,
                100,
                50,
                20,
                10,
                5,
                2,
                1
            };

        public static string Calculate()
        {
            int budget = 200;

            int count = calculateCoinCount(200, budget);
            return count.ToString();
        }

        static int calculateCoinCount(int valueLimit, int budget)
        {
            int count = 0;

            int value = _values.FirstOrDefault(x => x <= budget && x <= valueLimit);
            if (value == 0)
                return 0;

            if (value == 1)
            {
                Console.WriteLine("Budget {0}, only ones to spend.", budget);
                return 1;
            }

            if (value == budget)
            {
                Console.WriteLine("Budget: {0}, spent on {1}: +1",budget, value);
                count += 1; //za ovu
                count += calculateCoinCount(value - 1, budget); //za manje
            }
            else if (value < budget)
            {
                int remainder = budget;

                if (remainder > value)
                {
                    Console.WriteLine("Budget: {0}, spent on {1}", remainder, value);
                    remainder = remainder - value;          
                    count += calculateCoinCount(value, remainder);
                }

                //if (remainder == value)
                //    count++;

                count += calculateCoinCount(value - 1, budget);
            }

            return count;
        }
    }
}
